package com.msb.advanced;

/**
 * @author whf
 * @date 2025-02-27 20:14
 */
// https://leetcode.cn/problems/climbing-stairs/
public class ClimStairs爬楼梯问题 {
    
    public static int climStairs(int n) {
        // 转换成数学思想 fn = f(n -1) + f(n-2), 斐波那契函数
        // 初始值定义可以试一下
        int p = 0;
        int q = 0;
        int k = 1;
        for (int i = 1; i<=n; i++) {
            p = q;
            q = k;
            k = p + q;
        }
        return k;
    }


    public static int climStairs2(int n) {
        // 递归方法过不了leetcode, 时间过长, 因为重复计算了, 比如5拆成了4和3, 4又会拆出3, 
        // 可以通过map存下每次计算结果, 来优化这个递归
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climStairs2(n-1) + climStairs2(n-2);
    }

    public static void main(String[] args) {
        System.out.println(climStairs(44) == climStairs2(44));
    }
}
